package bintree;

import java.util.NoSuchElementException;

/**
 * 基于int的二分搜索树
 * @author yuisama
 * @date 2022/05/19 21:17
 **/
public class MyBinSearchTree {
    private int size;
    // 当前树的树根
    private Node root;

    public void add(int val) {
        root = add(root,val);
    }
    /**
     * 向当前以root为根的BST中插入一个新元素val，返回插入后的树根
     * @param root
     * @param val
     * @return
     */
    private Node add(Node root, int val) {
        if (root == null) {
            // 此时树为空，node就是树根
            Node node = new Node(val);
            size ++;
            return node;
        }
        if (val < root.val) {
            // 此时要在左子树中插入
            root.left = add(root.left,val);
        }
        if (val > root.val) {
            // 此时在右子树中插入
            root.right = add(root.right,val);
        }
        return root;
    }

    public boolean contains(int val) {
        return contains(root,val);
    }

    /**
     * 判断以当前root为根的BST中是否包含指定值val，存在返回true，否则返回false
     * @param root
     * @param val
     * @return
     */
    private boolean contains(Node root, int val) {
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        }
        else if (val < root.val) {
            return contains(root.left,val);
        }else {
            return contains(root.right,val);
        }
    }

    public int findMin() {
        if (size == 0) {
            throw new NoSuchElementException("bst is empty!no element!");
        }
        return min(root).val;
    }

    public int removeMin() {
        if (size == 0) {
            throw new NoSuchElementException("bst is empty!cannot remove");
        }
        Node minNode = min(root);
        root = removeMin(root);
        return minNode.val;
    }

    /**
     * 传入一颗以root为根的BST，就能删除其中的最小值，返回删除后的树根节点
     * @param root
     * @return
     */
    private Node removeMin(Node root) {
        if (root.left == null) {
            Node right = root.right;
            root.left = root.right = root = null;
            size --;
            return right;
        }
        root.left = removeMin(root.left);
        return root;
    }

    public int removeMax() {
        if (size == 0) {
            throw new NoSuchElementException("bst is empty!cannot remove");
        }
        Node max = max(root);
        root = removeMax(root);
        return max.val;
    }

    /**
     * 删除以root为根的BST中的最大值结点，返回删除后的树根节点
     * @param root
     * @return
     */
    private Node removeMax(Node root) {
        if (root.right == null) {
            // root就是待删除的节点
            Node left = root.left;
            root.left = root.right = root = null;
            size --;
            return left;
        }
        // 此时root不是待删除的节点，待删除的节点一定在右子树
        root.right = removeMax(root.right);
        return root;
    }

    /**
     * 在以root为根的BST中找到最小值结点
     * @param root
     * @return
     */
    private Node min(Node root) {
        if (root.left == null) {
            // 这个节点就是第一个碰到的左子树为空的结点
            return root;
        }
        return min(root.left);
    }

    public int findMax() {
        if (size == 0) {
            throw new NoSuchElementException("bst is empty!no element!");
        }
        return max(root).val;
    }

    /**
     * 在以root为根的BST中找到最小值结点
     * @param root
     * @return
     */
    private Node max(Node root) {
        if (root.right == null) {
            // 这个节点就是第一个碰到的右子树为空的结点
            return root;
        }
        return max(root.right);
    }

    public void remove(int val) {
        if (size == 0) {
            throw new NoSuchElementException("bst is empty!cannot remove");
        }
        root = remove(root,val);
    }

    /**
     * 在当前以root为根的BST中删除值为val的结点
     * 返回删除后的新的树根节点
     * @param root
     * @param val
     * @return
     */
    private Node remove(Node root, int val) {
        if (root == null) {
            // 将树中所有节点全都遍历一遍以后还没找到值为val的结点，节点根本不存在！
            throw new NoSuchElementException("bst has not this node!");
        }else if (val < root.val) {
            // 在左子树中删除
            root.left = remove(root.left,val);
            return root;
        }else if (val > root.val) {
            // 在右子树中删除
            root.right = remove(root.right,val);
            return root;
        }else {
            // 树不为空，且root.val == val
            // 当前root就是待删除的节点
            if (root.left == null) {
                // 当前待删除节点的左树为空，类似删除最小值,返回右子树的树根
                Node right = root.right;
                root.right = root = null;
                size --;
                return right;
            }
            if (root.right == null) {
                // 右树为空，类似于删除最大值，返回左子树的树根
                Node left = root.left;
                root.left = root = null;
                size --;
                return left;
            }
            // 这个待删除的结点左子树和右子树都不为空，Hibbard Deletion
            // 找到当然root的后继结点，右子树的最小值结点
            Node successor = min(root.right);
            // 1.先在右子树中删除这个节点
            successor.right = removeMin(root.right);
            // 2.连接root.left
            successor.left = root.left;
            // gc
            root.left = root.right = root = null;
            return successor;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        generateBSTString(root,0,sb);
        return sb.toString();
    }

    /**
     * 按照先序遍历的方式，将BST的节点值存入到sb之中
     * @param root
     * @param height
     * @param sb
     */
    private void generateBSTString(Node root, int height, StringBuilder sb) {
        // 边界
        if (root == null) {
            sb.append(generateHeightStr(height)).append("NULL\n");
            return;
        }
        sb.append(generateHeightStr(height)).append(root.val).append("\n");
        // 递归打印左子树
        generateBSTString(root.left,height + 1,sb);
        generateBSTString(root.right,height + 1,sb);
    }

    /**
     * 按照当前节点的高度打印 --
     * root.left => --
     * 第二层 ----
     * @param height
     * @return
     */
    private String generateHeightStr(int height) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < height; i++) {
            sb.append("--");
        }
        return sb.toString();
    }
}

class Node {
    int val;
    Node left;
    Node right;
    public Node(int val) {
        this.val = val;
    }
}